Run-time parallelization of loops that have irregular read-write memory access patterns is of interest to those working in computer science, given the increasing importance of parallel computing. For a recent overview of run-time parallelization, refer to L Rauchwerger, Run-time parallelization: It's time has come, Journal of Parallel Computing, special issue on languages and compilers for parallel computers, vol 24, pp 527 to 556 (1998).
Irregular loops in computer programs can have static read-write access patterns, which are defined at the beginning of execution by reading an input file (that is, an appropriate data set). Once the data is initially read, the access pattern does not change, but is nevertheless not available at compile-time. As noted in section 1.1 of Rauchwerger, state-of-the-art compilers cannot, in general, analyze and extract parallelism from irregular loops having static memory access patterns at compile-time.
Dynamic memory access patterns (which are computation dependent and are modified from one execution phase to another) require speculative parallelization and are not considered herein.
One recent reference relating to parallelism is T C Huang, P H Hsu and C F Wu, An efficient run-time scheme for exploiting parallelism on multiprocessor systems, in M Valero, V K Prasanna, and S Vajapeyam (eds): HiPC 2000, Lecture Notes in Computer Science, Vol 1970, pp 27–36 (2000), Springer-Verlag (Proceedings of the 7th International Conference on High Performance Computing, Bangalore, India, December 2000). The content of this reference is hereby incorporated by cross-reference.
Huang et al propose an efficient inspector/scheduler/executor algorithm for parallelizing irregular loops using a single array that has a single array element read or written during each pass through the loop. Each such “pass through” is referred to herein as an “iteration”. The memory access pattern, in the algorithm proposed by Huang et al, is statically defined.